package main

import (
	"fmt"
	"go-study/algorithm/standard"
)

// 如何在二叉树中找出与输入整数相等的所有路径

func main() {
	root := createTree()
	findRoad(root, 8, 0, make([]int, 0))
}

// 打印出满足所有节点数据的和等于 num 的所有路径
// root：（子）二叉树的根节点
// num：给定的整数
// sum：当前路径上所有节点的和
// v：用来存储从根节点到当前遍历到节点的路径
func findRoad(root *standard.BNode, num, sum int, v []int) {
	sum += root.Data.(int)
	v = append(v, root.Data.(int))

	// 当前节点是叶子节点且遍历的路径上所有节点的和等于 num
	if root.LeftChild == nil && root.RightChild == nil && sum == num {
		for _, v := range v {
			fmt.Print(v, " ")
		}
		fmt.Println()
	}

	// 遍历 root 的左子树
	if root.LeftChild != nil {
		findRoad(root.LeftChild, num, sum, v)
	}

	// 遍历 root 的右子树
	if root.RightChild != nil {
		findRoad(root.RightChild, num, sum, v)
	}

	// 清除遍历的路径
	sum -= v[len(v)-1]
	v = v[:len(v)-1]
}

func createTree() *standard.BNode {
	root := &standard.BNode{}
	node1 := &standard.BNode{}
	node2 := &standard.BNode{}
	node3 := &standard.BNode{}
	node4 := &standard.BNode{}

	root.Data = 6
	node1.Data = 3
	node2.Data = -7
	node3.Data = -1
	node4.Data = 9

	root.LeftChild = node1
	root.RightChild = node2
	node1.LeftChild = node3
	node1.RightChild = node4

	return root
}
